#include <unordered_map>
class Solution {
public:
    unordered_map<TreeNode*, int> ht;
    int depth(TreeNode* root) {
        if (!root) return 0;
        if (ht.find(root) != ht.end()) return ht[root];
        int ldep = depth(root->left);
        int rdep = depth(root->right);
        return ht[root] = max(ldep, rdep) + 1;
    }

    bool judge(TreeNode* root) {
        if (!root) return true;
        return (abs(ht[root->left] - ht[root->right]) <= 1 && judge(root->left) && judge(root->right));
    }
 
    bool IsBalanced_Solution(TreeNode* root) {
        depth(root);
        return judge(root);
    }
};